#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

//排序数组
void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

int GetMid(int* a, int left, int right)
{
    int mid = (left + right) / 2;
    if (a[left] < a[mid])
    {
        if (a[mid] < a[right])
            return mid;
        else if (a[left] > a[right])
            return left;
        else
            return right;
    }
    else//a[left] > a[mid]
    {
        if (a[mid] > a[right])
            return mid;
        else if (a[right] > a[left])
            return left;
        else
            return right;
    }
}
void QuickSort(int* a, int begin, int end)
{
    int left = begin;
    int right = end;
    if (left >= right)
        return;
    int midi = GetMid(a, left, right);
    Swap(&a[left], &a[right]);
    int cur = left + 1;
    int key = a[left];
    while (cur <= right)
    {
        if (a[cur] < key)
        {
            Swap(&a[cur], &a[left]);
            left++;
            cur++;
        }
        else if (a[cur] > key)
        {
            Swap(&a[cur], &a[right]);
            right--;
        }
        else
            cur++;
    }
    QuickSort(a, begin, left - 1);
    QuickSort(a, right + 1, end);
}

int* sortArray(int* nums, int numsSize, int* returnSize)
{
    int begin = 0;
    int end = numsSize;
    QuickSort(nums, begin, end - 1);
    *returnSize = numsSize;
    return nums;
}